package org.basis.algorithm.tree;

import org.basis.algorithm.tree.common.TreeNode;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * 检查二叉树
 *
 * @author Mr_wenpan@163.com 2021/12/20 23:02
 */
public class CheckBinaryTree {

    public static void main(String[] args) {
        final int a = 2 << 1;
        final int b = 2 << 2;
        final int c = 2 << 3;
        final int d = 1 << 3;
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
        System.out.println(d);
    }

    /**
     * 使用套路判断是否是搜索二叉树
     */
    public static boolean isBst(TreeNode<Integer> head) {

        return false;
    }

    /**
     * 是否是完全二叉树（从左到右依次变满的树）
     * 第一个左右节点不双全的节点以后所有的节点都应该是叶子节点，如果有左右孩子不双全的节点，那么这个节点要么只有左孩子要么左右孩子都没有
     */
    public static boolean isCompleteBinaryTree(TreeNode<Integer> head) {
        if (head == null) {
            return true;
        }
        // 宽度优先遍历二叉树
        LinkedList<TreeNode<Integer>> queue = new LinkedList<>();
        boolean isLeaf = false;
        queue.add(head);
        while (!queue.isEmpty()) {
            TreeNode<Integer> pollFirst = queue.pollFirst();
            if (pollFirst.left != null) {
                queue.add(pollFirst.left);
            }
            if (pollFirst.right != null) {
                queue.add(pollFirst.right);
            }
            // 检查弹出的节点
            if (isLeaf && (pollFirst.left != null || pollFirst.right != null)) {
                return false;
            }
            // 只要有一个节点为空，则后面的节点都应该是叶子节点
            if (pollFirst.left == null || pollFirst.right == null) {
                isLeaf = true;
                // 并且如果有一个节点不为空，那么这个节点只能是左节点
                if (pollFirst.right != null) {
                    return false;
                }
            }

        }
        return true;
    }

    /**
     * 是否是满二叉树，满二叉树可以通过节点个数于树的层高的关系公式来判断
     * 深度为k的二叉树，最多有2^k-1个节点
     */
    public static boolean isFullTree(TreeNode<Integer> head) {
        if (head == null) {
            return true;
        }
        // 求树的高度
        LinkedList<TreeNode<Integer>> queue = new LinkedList<>();
        queue.add(head);
        HashMap<TreeNode<Integer>, Integer> map = new HashMap<>();
        map.put(head, 1);
        // 树的节点个数
        int nodeCount = 1;

        // 宽度优先遍历求树的高度和节点个数
        while (!queue.isEmpty()) {
            TreeNode<Integer> poll = queue.poll();
            TreeNode<Integer> left = poll.left;
            TreeNode<Integer> right = poll.right;
            if (left != null) {
                queue.add(left);
                map.put(left, map.get(poll) + 1);
                nodeCount++;
            }
            if (right != null) {
                queue.add(right);
                map.put(right, map.get(poll) + 1);
                nodeCount++;
            }
        }

        // map中value中最大值就是树的最大高度
        int max = Integer.MIN_VALUE;
        for (Integer value : map.values()) {
            max = max > value ? max : value;
        }

        // 判断树高 + 节点个数是否满足公式 (2^k - 1)
        int res = (1 << max) - 1;

        return res == nodeCount;
    }


    public static boolean isFullTree2(TreeNode<Integer> head) {
        // 递归向左右树要信息
        FullTreeResult result = isFullTreeProcess(head);
        // 判断整棵树的节点个数和高度关系
        int height = result.height;
        int nodeCount = result.nodeCount;

        return nodeCount == ((1 << height) - 1);
    }

    /**
     * 使用二叉树套路求解一棵树是否是满二叉树
     * 递归，对于每个子树都向他的左右孩子要数据，然后整合数据向自己的父节点返回
     */
    public static FullTreeResult isFullTreeProcess(TreeNode<Integer> head) {
        // base case
        if (head == null) {
            return new FullTreeResult(0, 0);
        }
        // 问左右孩子要信息
        FullTreeResult leftResult = isFullTreeProcess(head.left);
        FullTreeResult rightResult = isFullTreeProcess(head.right);
        // 整合信息并向上返回
        int curNodeCount = leftResult.nodeCount + rightResult.nodeCount + 1;
        int height = Math.max(leftResult.height, rightResult.height) + 1;

        return new FullTreeResult(curNodeCount, height);
    }

    /**
     * 是否是平衡树
     */
    public static boolean isBalancedTree(TreeNode<Integer> head) {
        if (head == null) {
            return true;
        }
        BalanceTreeResult result = isBalancedTreeProcess(head);
        return result.isBalance;
    }

    public static BalanceTreeResult isBalancedTreeProcess(TreeNode<Integer> head) {
        // base case
        if (head == null) {
            return new BalanceTreeResult(true, 0);
        }
        // 问左右孩子要信息
        BalanceTreeResult leftResult = isBalancedTreeProcess(head.left);
        BalanceTreeResult rightResult = isBalancedTreeProcess(head.right);

        // 根据左右节点的信息构建自己的信息
        // 左右孩子必须都是平衡树，并且左右孩子树高差不能超过1
        boolean isBalance = (leftResult.isBalance && rightResult.isBalance) && Math.abs((leftResult.height - rightResult.height)) <= 1;
        // 自己的高度为左右孩子高度最高的那个 + 1
        int height = Math.max(leftResult.height, rightResult.height) + 1;

        return new BalanceTreeResult(isBalance, height);
    }

    /**
     * 是否是平衡树返回结果
     */
    static class BalanceTreeResult {
        boolean isBalance;
        int height;

        public BalanceTreeResult(boolean isBalance, int height) {
            this.isBalance = isBalance;
            this.height = height;
        }
    }

    /**
     * 是否是满二叉树返回结果
     */
    static class FullTreeResult {
        int nodeCount;
        int height;

        public FullTreeResult(int nodeCount, int height) {
            this.height = height;
            this.nodeCount = nodeCount;
        }
    }
}
